package middle;

import java.util.ArrayList;
import java.util.List;

public class Solution_78 {

    private List<List<Integer>> res;

    public List<List<Integer>> subsets(int[] nums) {
        int count = 1 << nums.length;
        res = new ArrayList<>(count);
        res.add(new ArrayList<>());
        dps(new ArrayList<>(), nums, 0);
        return res;
    }

    private void dps(List<Integer> list, int[] nums, int index) {
        if (index < nums.length) {
            List<Integer> copy_old = new ArrayList<>(list);
            dps(copy_old, nums, index + 1);

            List<Integer> copy_new = new ArrayList<>(list);
            copy_new.add(nums[index]);
            res.add(copy_new);
            dps(copy_new, nums, index + 1);
        }
    }

    public static void main(String[] args) {
        Solution_78 model = new Solution_78();
//        List<List<Integer>> lists = model.subsets(new int[]{1, 2, 3});
//        List<List<Integer>> lists = model.subsets(new int[]{0});
        List<List<Integer>> lists = model.subsets(new int[]{1, 2, 3, 4});
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
}
